#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
using std::cout;
using std::endl;
using std::unordered_map;

typedef std::pair<const char*, int> PAIR_CCI;

bool MyCompare(const PAIR_CCI& left, const PAIR_CCI& right) {
  return left.second > right.second;
}

// 假设我们有 10 万条 URL 访问日志，如何按照访问次数给 URL 排序？
void LargeUrlsCountSort(const char* urls[], int size) {
  unordered_map<const char*, int> hash;
  for (int i = 0; i < size; ++i) {
    auto iter = hash.find(urls[i]);
    if (iter == hash.end()) {
      // hash[urls[i]] = 1;
      hash.insert({urls[i], 1});
      // hash.insert(std::make_pair<const char*&, int>(urls[i], 1));
    } else {
      iter->second += 1;
    }
  }

  // 直接用sort对map排序是做不到的.可以把map装进pair里,然后将pair放入vector,自定义sort实现排序
  std::vector<PAIR_CCI> vec(hash.begin(), hash.end());
  std::sort(vec.begin(), vec.end(), MyCompare);

  for (auto it = hash.begin(); it != hash.end(); ++it) {
    cout << it->first << ":" << it->second << ", ";
  }
  cout << endl;

  // for (auto it = vec.begin(); it != vec.end(); ++it) {
  //   cout << it->first << ":" << it->second << ", ";
  // }
  for (const auto& item : vec) {
    cout << item.first << ":" << item.second << ", ";
  }
  cout << endl;

  // 或者转存到数组里（结构体保存url/count），自己排

  // 知识点：hash table里的元素不仅包含value，还包含key。
  // 1.通过要查找的key hash到数组idx，O(1)时间复杂度定位位置
  // 2.遍历该bucket链表，依次比较 判断是否存在要查找的key
  // 3.如果存在相等key则返回对应的value; 如果遍历到尾后则判定不存在
}

void TestLargeUrlsCountSort() {
  const char* urls[] = {"www.abc.com", "nihao.com",   "aaa.com",    "aaa.com",
                        "bbbb.com",    "www.abc.com", "www.abc.com"};
  LargeUrlsCountSort(urls, sizeof(urls) / sizeof(const char*));
}

int main() { TestLargeUrlsCountSort(); }